Spiral Matrix Series

发表于

Spiral Matrix I

Question

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Analysis

利用四个变量colbegin,colend,rowbegin,rowend来记录遍历的每天边上次走到的位置，在遍历完某行某列之后，向内（加1减1操作）移动该边。

  • 两个end的标记为长度-1，否则会导致数组的越界
  • 在从下往上遍历的时候需要检查之前的操作后边界是否有重合，假如有重合的话跳过

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res=new ArrayList<>();
        if(matrix.length==0)    return res;
        int rowbegin=0,colbegin=0,rowend=matrix.length-1,colend=matrix[0].length-1;
        
        while(rowbegin<=rowend&&colbegin<=colend){
            //Traverse from left to right
            for(int i=colbegin;i<=colend;i++){
                res.add(matrix[rowbegin][i]);
            }
            rowbegin++;
            
            //Traverse from top to down (in right side)
            for(int i=rowbegin;i<=rowend;i++){
                res.add(matrix[i][colend]);
            }
            colend--;
            
            //Traverse from right to left (in down side)
            if(rowbegin<=rowend){
                for(int i=colend;i>=colbegin;i--){
                    res.add(matrix[rowend][i]);
                }
            }
            rowend--;
            
            //Traverse from down to top (in left side)
            if(colbegin<=colend){
                for(int i=rowend;i>=rowbegin;i--){
                    res.add(matrix[i][colbegin]);
                }
            }
            colbegin++;
        }
        return res;
    }
}

Spiral Matrix II

Question

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,

Given n = 3,

You should return the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Analysis

思路同上，反过来对数组进行填充

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res=new int[n][n];
        int rowbegin=0,colbegin=0,rowend=n-1,colend=n-1;
        int num=1;
        
        while(rowbegin<=rowend&&colbegin<=colend){
            //To right
            for(int i=colbegin;i<=colend;i++){
                res[rowbegin][i]=num++;
            }
            rowbegin++;
            
            //To down (In right side)
            for(int i=rowbegin;i<=rowend;i++){
                res[i][colend]=num++;
            }
            colend--;
            
            //To left (In bottom side)
            if(rowbegin<=rowend){
                for(int i=colend;i>=colbegin;i--){
                    res[rowend][i]=num++;
                }
            }
            rowend--;
            
            //To top (In left side)
            if(colbegin<=colend){
                for(int i=rowend;i>=rowbegin;i--){
                    res[i][colbegin]=num++;
                }
            }
            colbegin++;
        }
        return res;
    }
}